/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-09-20
 * Time: 14:43
 */
public class HashBuck {
    static class Node{
        public int key;
        public int val;
        public Node next;

        public Node(int key,int val){
            this.key=key;
            this.val=val;
        }
    }

    public Node[] hashTable=new Node[10];
    public int usedSize;

    public static final double DEFAULT_LOAD_FACTOR = 0.75f;

    public void push(int key,int val){
        int index=key % hashTable.length;
        //key重复的情况
        Node cur=hashTable[index];
        while(cur != null){
            if(cur.key == key){
                cur.val=val;
                return;
            }
            cur=cur.next;
        }
        //没有找到那个相同的key，那我现在要进行头插法
        Node node=new Node(key,val);
        node.next=hashTable[index];
        hashTable[index]=node;
        usedSize++;

        //这个时候看一下负载因子的大小，如果超过0，75就要扩容
        if(isFull()){
            resize();
        }
    }

    private void resize() {
        Node[] newHashTable=new Node[2*hashTable.length];
        for (int i = 0; i < hashTable.length; i++) {
            Node cur=hashTable[i];
            while(cur !=null){
                Node curN=cur.next;
                int newIndex= cur.key/newHashTable.length;
                //依旧头插法
                cur.next=newHashTable[newIndex];
                newHashTable[newIndex]=cur;
                cur=curN;
            }
        }

        hashTable=newHashTable;
    }
    private boolean isFull() {
        return usedSize*1.0/hashTable.length >= DEFAULT_LOAD_FACTOR;
    }

    public int getVal(int key){
        int index=key%hashTable.length;
        Node cur=hashTable[index];
        while(cur != null){
            if(cur.key == key){
                return cur.val;
            }
            cur=cur.next;
        }
        return -1;
    }
}
